package com.mango.algorithm;

import java.util.Arrays;

/**
 * KMP算法
 * @Author: mango
 * @Date: 2022/5/16 10:05 下午
 */
public class KMP {
    /**
     * 求一个字符数组的next数组（最大公共前缀后缀长度）
     * @param chars
     * @return
     */
    private static int[] getNextArray(char[] chars) {
        if(chars.length == 1){
            return new int[]{-1};
        }
        int[] next = new int[chars.length];
        // 初始化0位置为-1，1位置上为0
        next[0] = -1;
        next[1] = 0;
        // next数组的位置
        int i = 2;
        int cn = 0;
        while (i < chars.length){
            // 当前字符等于i-1位置的字符，则next数组里值=cn+1
            if (chars[i - 1] == chars[cn]) {
                next[i++] = ++cn;
            }else if(cn > 0) {
                // cn向前移动
                cn = next[cn];
            }else{
                // cn=0了，则无法向前移动，则next里的值为0
                next[i++] = 0;
            }
        }
        return next;
    }

    /**
     * kmp算法的字符串下标查找方法
     * @param str 数据字符串
     * @param sub 查找子字符串
     * @return 包含则返回匹配的第一个字符下标，没找到则返回-1
     */
    private static int indexOf(String str,String sub){
        if (str == null || sub == null || str.length() < 1 || str.length() < sub.length()) {
            return -1;
        }
        char[] strArr = str.toCharArray();
        char[] subArr = sub.toCharArray();

        int[] next = getNextArray(subArr);
        int i1 = 0;
        int i2 = 0;
        while (i1 < strArr.length && i2 < subArr.length){
            // 相等，都后移
            if(strArr[i1] == subArr[i2]){
                i1++;
                i2++;
            }else if(next[i2] == -1) {
                // 不相等，且前缀数组为-1，说明前移到0下标了，没法继续前移了
                i1++;
            } else {
                // 没有移动到0下标，则前移至前缀记录位置
                i2 = next[i2];// 前移
            }
        }
        // i1 或者 i2 有一个越界了
        return i2 == subArr.length ? i1 - i2 : -1;
    }

    public static void main(String[] args) {
        String str = "abbacdeabbad";
        int[] next = getNextArray(str.toCharArray());
        System.out.println(Arrays.toString(next));
        System.out.println(indexOf(str,"abbad"));
        System.out.println(str.indexOf("abbad"));
    }
}
